Câu 0
Câu 4121026
Số phép so sánh tối thiểu cần sử dụng để tìm ra cả giá trị lớn nhất lẫn giá trị nhỏ nhất của một dãy gồm {N} phần tử là bao nhiêu?
Ghi ra một số nguyên duy nhất là kết quả đáp án.
-----------------------------------------------------------
Gợi ý phương pháp: Chia dãy thành hai nửa, tìm min và max mỗi nửa rồi so sánh chúng với nhau để tổng hợp kết quả.
Xét mảng arr[lo..hi], mã giả để tìm min và max của mảng này như sau:
Algorithm: minmax(lo, hi)if hi – lo ≤ 1 then
return (max(arr[lo], arr[hi]), min((arr[lo], arr[hi]))
else
(max1, min1):= minmax(lo, ⌊((lo + hi)/2)⌋)
(max2, min2):= minmax(⌊((lo + hi)/2) + 1)⌋, hi)
return (max(max1, max2), min(min1, min2))
Đáp án: 100">
Câu 4092895
Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$.
Đáp án: 100">
Câu 4092853
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
Câu 4092854
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
Đáp án: 100
NP-đầy đủ
[0]
P
Câu 4092855
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này.
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
[0]
NP-đầy đủ
Đáp án: 100
P
Câu 4092856
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
Câu 4092857
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
Đáp án: 100
NP-đầy đủ
[0]
P
Câu 4092858
Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
[0]
NP-đầy đủ
Đáp án: 100
P
Câu 4092884
Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?
Đáp án: -50
Đồ thị tổng quát
Đáp án: 25
Đồ thị không chứa chu trình âm
Đáp án: 25
Đồ thị không có cạnh trọng số âm
Đáp án: 25
Đồ thị có hướng không có chu trình DAG
Đáp án: 25
Cây
Đáp án: -50
Đồ thị hai phía
Câu 4121027
Đáp án: 100
O(1)
[0]
O(n)
[0]
O(nlogn)
[0]
O(logn)
[0]
Không đáp án nào đúng
Câu 4121028
Trong các thuật toán dưới đây, thuật toán nào không phải là thuật toán chia
để trị?
Đáp án: 50
[0]
Sắp xếp nhanh
[0]
Sắp xếp trộn
[0]
Tìm kiếm nhị phân
Đáp án: 50
Câu 4121029
Đáp án: 100
O(logn)
[0]
O(n)
[0]
O(nlogn)
[0]
O(1)
[0]
O(log(logn))
[0]
Không đáp án nào đúng
Câu 4121030
Xét đa thức p(x) = a0 + a1*x + a2*x2 + a3*x3, trong đó ai! = 0, với mọi i. Số phép nhân tối thiểu cần thiết để tính giá trị của p(x) với đầu vào x bất kỳ?
Đáp án: 100
3
[0]
4
[0]
6
[0]
9
[0]
12
[0]
Đáp án khác
Câu 4121031
Điều nào sau đây là đúng về độ phức tạp thuật toán là nghiệm của hệ thức truy hồi T(n)=2T(n/2) + logn với T (1) = 1?
Đáp án: 100
O(n)
[0]
O(nlogn)
[0]
O(logn)
[0]
O(n2)
[0]
Không đáp án nào đúng
Câu 4121032
Cho mảng gồm các phần tử sau, 23, 32, 45, 69, 72, 73, 89, 97. Thuật toán sắp xếp nào dưới đây sử dụng ít phép so sánh nhất để sắp xếp mảng tăng dần?
[0]
Đáp án: 100
[0]
Merge sort
[0]
Quick sort sử dụng phần tử cuối cùng là phần tử pivot
Câu 4121033
Thuật toán dưới đây có chức năng gì?
Đáp án: 100
[0]
Tính tổng x+y
[0]
Tính phần dư của x chia cho y
[0]
Tìm bội số chung nhỏ nhất của x và y
[0]
Không đáp án nào đúng
Câu 4149876
Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.
Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
5
[0]
6
Câu 4121035
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
14
[0]
20
Đáp án: 100
18
[0]
Đáp án khác
Câu 4149877
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
14
[0]
20
Đáp án: 100
18
Câu 4121036
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
17
Đáp án: 100
21
[0]
27
[0]
Đáp án khác
Câu 4149878
Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.
Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?
[0]
7
[0]
17
Đáp án: 100
21
[0]
27
Câu 4121037
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án: 100
31
[0]
32
[0]
33
[0]
34
[0]
Đáp án khác
Câu 4149879
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án: 100
31
[0]
32
[0]
33
[0]
34
Câu 4121038
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
36
[0]
37
Đáp án: 100
38
[0]
40
[0]
42
[0]
Đáp án khác
Câu 4149880
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
36
[0]
37
Đáp án: 100
38
[0]
40
[0]
42
Câu 4121039
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án: 100
32
[0]
34
[0]
35
[0]
Đáp án khác
Câu 4149881
Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu?
[0]
30
Đáp án: 100
32
[0]
34
[0]
35
Câu 4121040
Cấu trúc dữ liệu Deque cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
[0]
vào một đầu, ra đầu còn lại
Đáp án: 100
vào và ra được từ cả hai đầu
[0]
vào và ra duy nhất một đầu
[0]
không cách nào trong các cách ở đây
[0]
Đáp án khác
Câu 4149813
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v]
Kết luận nào sau đây đúng?
Đáp án: 100
low[7] = 4 và num[7] = 7
[0]
low[7] = 7 và num[7] = 7
[0]
low[7] = 6 và num[7] = 7
[0]
low[7] = 5 và num[7] = 7
[0]
low[7] = 3 và num[7] = 5
Câu 4092802
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v]
Kết luận nào sau đây đúng?
Đáp án: 100
low[7] = 4 và num[7] = 7
[0]
low[7] = 7 và num[7] = 7
[0]
low[7] = 6 và num[7] = 7
[0]
low[7] = 5 và num[7] = 7
[0]
low[7] = 3 và num[7] = 5
Câu 4149814
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v]
Kết luận nào sau đây đúng?
Đáp án: 100
low[6] = 2, num[6] = 5
[0]
low[6] = 3, num[6] = 5
[0]
low[6] = 5, num[6] = 5
[0]
low[6] = 4, num[6] = 5
[0]
low[6] = 4, num[6] = 6
Câu 4092803
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v]
Kết luận nào sau đây đúng?
Đáp án: 100
low[6] = 2, num[6] = 5
[0]
low[6] = 3, num[6] = 5
[0]
low[6] = 5, num[6] = 5
[0]
low[6] = 4, num[6] = 5
[0]
low[6] = 4, num[6] = 6
Câu 4092885
Thuật toán Dijkstra tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?
Đáp án: -50
Đồ thị tổng quát
Đáp án: -25
Đồ thị không chứa chu trình âm
Đáp án: 50
Đồ thị không có cạnh trọng số âm
Đáp án: -25
Đồ thị có hướng không có chu trình DAG
Đáp án: 50
Cây
Đáp án: -25
Đồ thị hai phía
Câu 4121041
Một thuật toán duyệt toàn bộ được gọi là hiệu quả:
[0]
khi có độ phức tạp tính toán là hàm mũ
[0]
khi có độ phức tạp tính toán là đa thức
Đáp án: 50
khi có độ phức tạp tính toán là hằng số
[0]
khi có độ phức tạp khấu trừ là tuyến tính
Đáp án: 50
khi có độ phức tạp khấu trừ là hằng số
[0]
khi có độ phức tạp khấu trừ là đa thức
[0]
Không mệnh đề nào trong các mệnh đề ở đây thoả mãn
Câu 4149820
Phát biểu nào sau đây đúng với thuật toán sắp xếp nổi bọt cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092809
Phát biểu nào sau đây đúng với thuật toán sắp xếp nổi bọt cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4149821
Phát biểu nào sau đây đúng với thuật toán sắp xếp chèn cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092810
Phát biểu nào sau đây đúng với thuật toán sắp xếp chèn cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4149822
Phát biểu nào sau đây đúng với thuật toán sắp xếp trộn cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092811
Phát biểu nào sau đây đúng với thuật toán sắp xếp trộn cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4149823
Phát biểu nào sau đây đúng với thuật toán sắp xếp vun đống cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092812
Phát biểu nào sau đây đúng với thuật toán sắp xếp vun đống cho dãy gồm n phần tử
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4149824
Phát biểu nào sau đây đúng với thuật toán sắp xếp lựa chọn cho dãy gồm n phần tử
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092813
Phát biểu nào sau đây đúng với thuật toán sắp xếp lựa chọn cho dãy gồm n phần tử
Đáp án: 100
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n)
[0]
Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn)
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\))
[0]
Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\))
Câu 4092878
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
6
Câu 4092879
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
6
[0]
Không có phương án nào thực hiện được
Câu 4092880
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
2
[0]
3
Đáp án: 100
4
[0]
5
Câu 4092881
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
5
[0]
Không có phương án thực hiện
Câu 4121042
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
5
[0]
2
[0]
9
[0]
4
[0]
Đáp án khác
Câu 4149830
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
5
[0]
2
[0]
9
[0]
4
Câu 4121043
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}
for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
5
Đáp án: 100
7
[0]
6
[0]
4
[0]
Đáp án khác
Câu 4149831
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}
for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
5
Đáp án: 100
7
[0]
6
[0]
4
Câu 4121044
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
4
Đáp án: 100
3
[0]
2
[0]
5
[0]
Đáp án khác
Câu 4149832
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
4
Đáp án: 100
3
[0]
2
[0]
5
Câu 4121045
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
5
[0]
3
[0]
4
[0]
6
[0]
Đáp án khác
Câu 4149833
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
5
[0]
3
[0]
4
[0]
6
Câu 4121046
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
[0]
4
[0]
6
Đáp án: 100
5
[0]
Đáp án khác
Câu 4149834
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
[0]
4
[0]
6
Đáp án: 100
5
Câu 4121047
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
[0]
4
[0]
6
Đáp án: 100
7
[0]
Đáp án khác
Câu 4149835
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
[0]
4
[0]
6
Đáp án: 100
7
Câu 4121048
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
Đáp án: 100
5
[0]
2
[0]
7
[0]
Đáp án khác
Câu 4149836
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
1
Đáp án: 100
5
[0]
2
[0]
7
Câu 4121049
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
4
[0]
5
[0]
3
Đáp án: 100
7
[0]
Đáp án khác
Câu 4149837
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
4
[0]
5
[0]
3
Đáp án: 100
7
Câu 4092827
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian bắt đầu \(S_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?
Đáp án: -50
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án: 50
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án: 50
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
Đáp án: -50
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Câu 4092831
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không tăng của giá trị;
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và xếp đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\)).
Đáp án: 50
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)
Đáp án: -50
\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)
Đáp án: 50
\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)
Đáp án: -50
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)
Câu 4092828
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian kết thúc \(F_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?
Đáp án: 25
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Câu 4092832
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không giảm của trọng lượng;
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Đáp án: -50
\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án: 50
\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án: 50
\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)
Đáp án: -50
\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)
Câu 4092829
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của tổng thời gian thực hiện công việc \(F_j - S_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?
Đáp án: 50
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)
Đáp án: 50
\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)
Đáp án: -50
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)
Đáp án: -50
\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)
Câu 4092833
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng lượng (\(C_i /W_i\)), nghĩa là \[\frac {C_{i_1}}{W_{i_1}} \ge \frac {C_{i_2}}{W_{i_2}} \ge \ldots\le \frac {C_{i_n}}{W_{i_n}};\]
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Đáp án: -50
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)
Đáp án: 50
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)
Đáp án: -50
\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)
Đáp án: 50
\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)
Câu 4092830
Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Với mỗi công việc \(j\), tính \(C_j\) là số lượng công việc không tương thích với \(j\). Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của \(C_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?
Đáp án: 50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án: 50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)
Đáp án: -50
\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án: -50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Câu 4092834
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 3 có giá vé là 90 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 3 thành phố khác
- Bus từ thành phố 5 có giá vé là 20 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 6 có giá vé là 20 và có thể đi đến nhiều nhất 5 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
50
[0]
60
Đáp án: 100
70
[0]
80
[0]
90
Câu 4092835
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 3 có giá vé là 40 và có thể đi đến nhiều nhất 3 thành phố khác
- Bus từ thành phố 4 có giá vé là 60 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 5 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
40
Đáp án: 100
50
[0]
60
[0]
70
[0]
80
Câu 4092836
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 3 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 5 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
10
[0]
20
Đáp án: 100
30
[0]
40
[0]
50
Câu 4121050
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
Đáp án: 100
137
[0]
100
[0]
37
[0]
52
[0]
Đáp án khác
Câu 4149825
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
Đáp án: 100
137
[0]
100
[0]
37
[0]
52
Câu 4092814
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
Đáp án: 100
137
[0]
100
[0]
37
[0]
52
Câu 4121051
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
37
[0]
103
Đáp án: 100
11
[0]
42
[0]
Đáp án khác
Câu 4149826
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
37
[0]
103
Đáp án: 100
11
[0]
42
Câu 4092815
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
37
[0]
103
Đáp án: 100
11
[0]
42
Câu 4121052
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
30
Đáp án: 100
3
[0]
6
[0]
8
[0]
Đáp án khác
Câu 4149827
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
30
Đáp án: 100
3
[0]
6
[0]
8
Câu 4092816
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
30
Đáp án: 100
3
[0]
6
[0]
8
Câu 4121053
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
20
Đáp án: 100
4
[0]
5
[0]
9
[0]
Đáp án khác
Câu 4149828
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
20
Đáp án: 100
4
[0]
5
[0]
9
Câu 4092817
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
[0]
20
Đáp án: 100
4
[0]
5
[0]
9
Câu 4121054
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
10
[0]
4
[0]
6
Đáp án: 100
7
[0]
Đáp án khác
Câu 4149829
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
10
[0]
4
[0]
6
Đáp án: 100
7
Câu 4092818
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
[0]
10
[0]
4
[0]
6
Đáp án: 100
7
Câu 4121055
Phát biểu nào sau đây không đúng
Đáp án: 100
Các phần tử của danh sách liên kết luôn được cấp phát kế tiếp nhau trong bộ nhớ
[0]
Các phần tử của danh sách liên kết không nhất thiết được cấp phát kế tiếp nhau trong bộ nhớ
[0]
Không đáp án nào đúng
Câu 4121056
Phát biểu ”Ta truy nhập đến các phần tử của danh sách liên kết thông qua chỉ số” là đúng hay sai?
[0]
Đúng
Đáp án: 100
Sai
Câu 4121057
Phát biểu ”Thao tác tìm kiếm một phần tử trên danh sách liên kết có độ phức tạp trong tình huống tồi nhất là O(n) với n là số phần tử của danh sách liên kết” là đúng hay sai?
Đáp án: 100
Đúng
[0]
Sai
Câu 4149852
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 3 có kề nhau hay không?
Đáp án: 100
Có
[0]
Không
Câu 4092841
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 3 có kề nhau hay không?
Đáp án: 100
Có
[0]
Không
Câu 4149853
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 3 có kề nhau hay không?
[0]
Có
Đáp án: 100
Không
Câu 4092842
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 3 có kề nhau hay không?
[0]
Có
Đáp án: 100
Không
Câu 4149854
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 4 có kề nhau hay không?
Đáp án: 100
Có
[0]
Không
Câu 4092843
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 4 có kề nhau hay không?
Đáp án: 100
Có
[0]
Không
Câu 4149855
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 4 có kề nhau hay không?
[0]
Có
Đáp án: 100
Không
Câu 4092844
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 4 có kề nhau hay không?
[0]
Có
Đáp án: 100
Không
Câu 4121058
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đáp án: 100
Đúng
[0]
Sai
Câu 4149893
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đáp án: 100
Đúng
[0]
Sai
Câu 4092882
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đáp án: 100
Đúng
[0]
Sai
Câu 4121059
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
[0]
Sắp xếp chèn
Đáp án: 100
Sắp xếp lựa chọn
[0]
Sắp xếp nổi bọt
[0]
Sắp xếp vun đống
[0]
Đáp án khác
Câu 4149894
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
[0]
Sắp xếp chèn
Đáp án: 100
Sắp xếp lựa chọn
[0]
Sắp xếp nổi bọt
[0]
Sắp xếp vun đống
Câu 4092883
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
[0]
Sắp xếp chèn
Đáp án: 100
Sắp xếp lựa chọn
[0]
Sắp xếp nổi bọt
[0]
Sắp xếp vun đống
Câu 4121060
Trong các kỹ năng cơ bản dưới đây, kỹ năng nào cần rèn luyện trong khoá học?
[0]
Kỹ năng đọc đề
[0]
Kỹ năng phân loại bài toán
[0]
Kỹ năng kiểm thử chương trình
[0]
Kỹ năng phân tích thuật toán
Đáp án: 100
Tất cả các kỹ năng ở đây
Câu 4092865
Given a sequence \(a = a_1, a_2, …, a_n\). The subsequence of a is defined as the sequence obtained by removing some elements of a.
Given the sequence a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 and b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. You are asked to compute the length of the longest subsequence (i.e. the maximum number of elements) that is both a subsequence of a and a subsequence of b.
[0]
3
Đáp án: 100
4
[0]
5
[0]
6
Câu 4092845
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0]
26
[0]
27
Đáp án: 100
28
[0]
29
[0]
30
Câu 4092846
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
Đáp án: 100
24
[0]
25
[0]
26
[0]
27
[0]
28
Câu 4092847
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0]
16
Đáp án: 100
18
[0]
19
[0]
23
Câu 4121061
Giả sử độ phức tạp tính toán của giải thuật chia để trị khi giải một bài toán kích thước n có công thức truy hồi như sau:
$$ T(n) = 9 T(n/3) + n^2 $$
Dùng định lý thợ (master theorem), hãy xác định độ phức tạp tính toán của giải thuật trong trường hợp trên.
Đáp án: 100
\(\Theta(n^2logn) \)
[0]
\(\Theta(nlogn) \)
[0]
\(\Theta(n^2) \)
[0]
\(\Theta(nlog^2n) \)
[0]
Đáp án khác
Câu 4092868
[0]
30
Đáp án: 100
31
[0]
32
[0]
33
[0]
34
Câu 4092869
Given 9 elements 1, 2, …, 9 lying on a line, where the element i is at the coordinate i. The elements 1,2…, 9 have weight 6, 4, 9, 2, 5, 9, 10, 14, 6 respectively. You are asked to choose a subsequence S of element i1 < i2 < … < ik from these 9 elements such that the distance between 2 elements ij and ij+1 (j = 1, ..., k-1) is greater than or equal to 2 and is smaller or equal to 4 (2 <= ij+1 – ij <= 4) and the sum of the weight of these elements is maximum. What is this sum?
[0]
36
[0]
37
Đáp án: 100
38
[0]
40
[0]
42
Câu 4092870
Given 9 elements 1, 2, …, 9 lying on a line, where the element i is at the coordinate i. The elements 1,2…, 9 have weight 2, 6, 8, 1, 7, 4, 10, 4, 5 respectively. You are asked to choose a subsequence S of element i1 < i2 < … < ik from these 9 elements such that the distance between 2 elements ij and ij+1 (j = 1, ..., k-1) is greater than or equal to 2 and is smaller or equal to 4 (2 <= ij+1 – ij <= 4) and the sum of the weight of these elements is maximum. What is this sum?
[0]
30
Đáp án: 100
32
[0]
34
[0]
35
Câu 4092867
Given the sequence a = a[1], a[2], …, a[n]. A subsequence of a is defined as a sequence a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), whose weight is the sum of its elements.
Given the sequence 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. You are asked to compute the weight of the subsequence with the maximum weight.
[0]
7
[0]
17
Đáp án: 100
21
[0]
27
Câu 4092866
Given the sequence a = a[1], a[2], …, a[n]. A subsequence of a is defined as a sequence a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), whose weight is the sum of its elements.
Given the sequence 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. You are asked to compute the weight of the subsequence with the maximum weight.
[0]
7
[0]
14
[0]
20
Đáp án: 100
18
Câu 4149806
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
1,2,3,4,5
Đáp án: 100
1,2,5,3,4
[0]
1,3,4,2,5
[0]
1,4,3,2,5
Câu 4092795
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
1,2,3,4,5
Đáp án: 100
1,2,5,3,4
[0]
1,3,4,2,5
[0]
1,4,3,2,5
Câu 4149807
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
2,1,5,3,4
Đáp án: 100
2,1,3,4,5
[0]
2, 3, 4, 1, 5
[0]
2, 5, 4, 1, 3
Câu 4092796
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
2,1,5,3,4
Đáp án: 100
2,1,3,4,5
[0]
2, 3, 4, 1, 5
[0]
2, 5, 4, 1, 3
Câu 4149808
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
3, 1, 2, 4, 5
Đáp án: 100
3, 2, 4, 1, 5
[0]
3, 2, 4, 5, 1
[0]
3, 5, 4, 2, 1
Câu 4092797
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
3, 1, 2, 4, 5
Đáp án: 100
3, 2, 4, 1, 5
[0]
3, 2, 4, 5, 1
[0]
3, 5, 4, 2, 1
Câu 4149809
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
4, 1, 2, 3, 5
[0]
4, 5, 1, 2, 3
Đáp án: 100
4, 3, 2, 1, 5
[0]
4, 3, 2, 5, 1
Câu 4092798
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
4, 1, 2, 3, 5
[0]
4, 5, 1, 2, 3
Đáp án: 100
4, 3, 2, 1, 5
[0]
4, 3, 2, 5, 1
Câu 4149810
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
Đáp án: 100
5, 1, 2, 3, 4
[0]
5, 2, 1, 4, 3
[0]
5, 3, 4, 1, 2
[0]
5, 4, 3, 2, 1
Câu 4092799
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
Đáp án: 100
5, 1, 2, 3, 4
[0]
5, 2, 1, 4, 3
[0]
5, 3, 4, 1, 2
[0]
5, 4, 3, 2, 1
Câu 4149815
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
Đáp án: 100
1,2,3,4,5
[0]
1,2,5,3,4
[0]
1,3,4,2,5
[0]
1,4,3,2,5
Câu 4092804
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
Đáp án: 100
1,2,3,4,5
[0]
1,2,5,3,4
[0]
1,3,4,2,5
[0]
1,4,3,2,5
Câu 4149816
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
2, 3, 4, 5, 1
Đáp án: 100
2, 1, 5, 3, 4
[0]
2, 3, 4, 5, 1
[0]
2, 1, 3, 4, 5
Câu 4092805
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
2, 3, 4, 5, 1
Đáp án: 100
2, 1, 5, 3, 4
[0]
2, 3, 4, 5, 1
[0]
2, 1, 3, 4, 5
Câu 4149817
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
3, 2, 4, 5, 1
Đáp án: 100
3, 2, 1, 5, 4
[0]
3, 2, 4, 1, 5
[0]
3, 1, 2, 4, 5
Câu 4092806
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
3, 2, 4, 5, 1
Đáp án: 100
3, 2, 1, 5, 4
[0]
3, 2, 4, 1, 5
[0]
3, 1, 2, 4, 5
Câu 4149818
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
4, 2, 3, 5, 1
Đáp án: 100
4, 2, 1, 5, 3
[0]
4, 3, 2, 5, 1
[0]
4, 1, 2, 3, 5
Câu 4092807
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
4, 2, 3, 5, 1
Đáp án: 100
4, 2, 1, 5, 3
[0]
4, 3, 2, 5, 1
[0]
4, 1, 2, 3, 5
Câu 4149819
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
5, 4, 3, 2, 1
Đáp án: 100
5, 1, 2, 4, 3
[0]
5, 3, 4, 2, 1
[0]
5, 1, 3, 4, 2
Câu 4092808
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
[0]
5, 4, 3, 2, 1
Đáp án: 100
5, 1, 2, 4, 3
[0]
5, 3, 4, 2, 1
[0]
5, 1, 3, 4, 2
Câu 4149859
Cho dãy 1, 4, 3, 6, 7, 2, 5 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
Đáp án: 100
7, 4, 6, 2, 3, 5, 1
[0]
1, 2, 3, 4, 5, 6, 7
[0]
2, 1, 4, 3, 6, 7, 5
[0]
5, 3, 1, 7, 6, 2, 4
Câu 4092848
Cho dãy 1, 4, 3, 6, 7, 2, 5 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
Đáp án: 100
7, 4, 6, 2, 3, 5, 1
[0]
1, 2, 3, 4, 5, 6, 7
[0]
2, 1, 4, 3, 6, 7, 5
[0]
5, 3, 1, 7, 6, 2, 4
Câu 4149860
Cho dãy 1, 4, 8, 6, 3, 5, 2 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
1, 2, 3, 4, 5, 8, 6
[0]
1, 2, 4, 3, 6, 8, 5
Đáp án: 100
8, 4, 6, 2, 3, 5, 1
[0]
3, 5, 1, 8, 6, 2, 4
Câu 4092849
Cho dãy 1, 4, 8, 6, 3, 5, 2 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
1, 2, 3, 4, 5, 8, 6
[0]
1, 2, 4, 3, 6, 8, 5
Đáp án: 100
8, 4, 6, 2, 3, 5, 1
[0]
3, 5, 1, 8, 6, 2, 4
Câu 4149861
Cho dãy 2, 4, 8, 6, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 4, 5, 8, 6
[0]
7, 2, 4, 3, 6, 8, 5
Đáp án: 100
8, 5, 7, 2, 3, 4, 6
[0]
3, 5, 7, 8, 4, 2, 6
Câu 4092850
Cho dãy 2, 4, 8, 6, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 4, 5, 8, 6
[0]
7, 2, 4, 3, 6, 8, 5
Đáp án: 100
8, 5, 7, 2, 3, 4, 6
[0]
3, 5, 7, 8, 4, 2, 6
Câu 4149862
Cho dãy 2, 4, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 4, 5, 8, 1
[0]
8, 2, 4, 3, 1, 7, 5
Đáp án: 100
8, 5, 7, 2, 3, 4, 1
[0]
3, 5, 7, 8, 4, 2, 1
Câu 4092851
Cho dãy 2, 4, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 4, 5, 8, 1
[0]
8, 2, 4, 3, 1, 7, 5
Đáp án: 100
8, 5, 7, 2, 3, 4, 1
[0]
3, 5, 7, 8, 4, 2, 1
Câu 4149863
Cho dãy 2, 6, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 6, 5, 8, 1
[0]
8, 2, 6, 3, 1, 7, 5
[0]
3, 5, 7, 8, 6, 2, 1
Đáp án: 100
8, 5, 7, 2, 3, 6, 1
Câu 4092852
Cho dãy 2, 6, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
[0]
7, 2, 3, 6, 5, 8, 1
[0]
8, 2, 6, 3, 1, 7, 5
[0]
3, 5, 7, 8, 6, 2, 1
Đáp án: 100
8, 5, 7, 2, 3, 6, 1
Câu 4121062
Trong các mục tiêu dưới đây, đâu là mục tiêu chính của môn học Thuật toán ứng dụng? (Có thể trả lời nhiều đáp án)
Đáp án: 25
Tăng cường khả năng mô hình hoá bài toán thực tế
Đáp án: 25
Tăng cường kỹ năng đề xuất Cấu trúc dữ liệu và Thuật toán cho các bài toán thực tế
Đáp án: 25
Tăng cường kỹ năng chuyển hoá thiết kế Cấu trúc dữ liệu và Thuật toán sang
chương trình có thể chạy được và đúng
Đáp án: 25
Tăng cường kỹ năng lập trình ngôn ngữ
[0]
Tăng cường kỹ năng phân tích, thiết kế các hệ thống thông tin lớn
Câu 4149850
Kết luận nào sau đây đúng với hàng đợi?
[0]
Phần tử nào được đưa vào hàng đợi đầu tiên thì sẽ được lấy ra cuối cùng.
Đáp án: 100
Phần từ nào đưa vào hàng đợi cuối cùng thì sẽ được lấy ra cuối cùng.
Câu 4149851
Kết luận nào sau đây đúng với hàng đợi?
Đáp án: 100
Hàng đợi là cấu trúc tuyến tính
[0]
Hàng đợi là cấu trúc phân cấp, dạng cây
Câu 4092839
Kết luận nào sau đây đúng với hàng đợi?
[0]
Phần tử nào được đưa vào hàng đợi đầu tiên thì sẽ được lấy ra cuối cùng.
Đáp án: 100
Phần từ nào đưa vào hàng đợi cuối cùng thì sẽ được lấy ra cuối cùng.
Câu 4092840
Kết luận nào sau đây đúng với hàng đợi?
Đáp án: 100
Hàng đợi là cấu trúc tuyến tính
[0]
Hàng đợi là cấu trúc phân cấp, dạng cây
Câu 4149848
Kết luận nào sau đây đúng với ngăn xếp?
Đáp án: 100
Phần tử nào được đưa vào ngăn xếp đầu tiên thì sẽ được lấy ra cuối cùng.
[0]
Phần từ nào đưa vào ngăn xếp cuối cùng thì sẽ được lấy ra cuối cùng.
Câu 4149849
Kết luận nào sau đây đúng với ngăn xếp?
Đáp án: 100
Ngăn xếp là cấu trúc tuyến tính
[0]
Ngăn xếp là cấu trúc phân cấp, dạng cây.
Câu 4092837
Kết luận nào sau đây đúng với ngăn xếp?
Đáp án: 100
Phần tử nào được đưa vào ngăn xếp đầu tiên thì sẽ được lấy ra cuối cùng.
[0]
Phần từ nào đưa vào ngăn xếp cuối cùng thì sẽ được lấy ra cuối cùng.
Câu 4092838
Kết luận nào sau đây đúng với ngăn xếp?
Đáp án: 100
Ngăn xếp là cấu trúc tuyến tính
[0]
Ngăn xếp là cấu trúc phân cấp, dạng cây.
Câu 4121063
Giả sử cho trước hàm sau:
int partition (int a[], int n);
Hàm này lấy phần tử đầu tiên của mảng a[] làm phần tử chốt, sau đó sắp xếp các phần tử nhỏ hơn hoặc bằng phần từ chốt về phần bên trái của mảng, và tất cả phần tử lớn hơn phần tử chốt về phần bên phải của mảng. Ngoài ra, hàm cũng di chuyển phần tử chốt về vị trí cuối cùng của phần bên trái. Hàm trả về số lượng phần tử của phần bên trái.
Đoạn chương trình C bị khuyết sau sử dụng hàm partition function để tìm phần tử nhỏ thứ k trong mảng a[] kích thước n (giả định k ≤ n). Hãy lựa chọn phần danh sách tham số đúng trong các phương án dưới đây để điền vào chỗ trống.
int kth_smallest (int a[], int n, int k) {
int left_end = partition (a, n);
if (left_end+1==k){
return a [left_end];
}
if (left_end+1 > k) {
return kth_smallest (____________________);
}
else {
return kth_smallest (____________________);
}
}Đáp án: 100
(a, left_end, k) và (a+left_end+1, n–left_end–1, k–left_end–1)
[0]
(a, left_end, k) và (a, n–left_end–1, k–left_end–1)
[0]
(a, left_end+1, N–left_end–1, K–left_end–1) và (a, left_end, k)
[0]
(a, n–left_end–1, k–left_end–1) và (a, left_end, k)
[0]
Đáp án khác
Câu 4149870
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(nlogn)\)
Câu 4149871
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
[0]
\(O(logn)\)
[0]
\(O(n)\)
Đáp án: 100
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4149872
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4149873
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
Đáp án: 100
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4149874
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
[0]
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
Đáp án: 100
\(O(logn)\)
Câu 4149875
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
[0]
\(O(nlogn)\)
Đáp án: 100
\(O(n)\)
[0]
\(O(n^2)\)
Câu 4092859
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(nlogn)\)
Câu 4092860
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
[0]
\(O(logn)\)
[0]
\(O(n)\)
Đáp án: 100
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4092861
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4092862
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
Đáp án: 100
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
Câu 4092863
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
[0]
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
Đáp án: 100
\(O(logn)\)
Câu 4092864
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
[0]
\(O(nlogn)\)
Đáp án: 100
\(O(n)\)
[0]
\(O(n^2)\)
Câu 4121064
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(nlogn)\)
[0]
Đáp án khác
Câu 4121065
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
[0]
\(O(nlogn)\)
Đáp án: 100
\(O(n)\)
[0]
\(O(n^2)\)
[0]
Đáp án khác
Câu 4121066
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
[0]
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
Đáp án: 100
\(O(logn)\)
[0]
Đáp án khác
Câu 4121067
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
Đáp án: 100
\(O(log(logn))\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
[0]
Đáp án khác
Câu 4121068
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
Đáp án: 100
\(O(logn)\)
[0]
\(O(n)\)
[0]
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
[0]
Đáp án khác
Câu 4121069
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
[0]
\(O(logn)\)
[0]
\(O(n)\)
Đáp án: 100
\(O(n^\frac {1}{2})\)
[0]
\(O(nlogn)\)
[0]
Đáp án khác
Câu 4092886
Những mệnh đề nào sau đây là ĐÚNG?
Đáp án: 50
Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó
Đáp án: -50
Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó
Đáp án: -50
Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)
Đáp án: 50
Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)
Câu 4121070
Thuật toán chia để trị thường được lập trình theo phương pháp nào sau đây?
Đáp án: 100
Đệ quy
[0]
Dùng các vòng lặp
[0]
Quay lui
[0]
Dùng cú pháp lambda
[0]
Đáp án khác
Câu 4092887
Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?
Đáp án: -25
Nhánh cận
Đáp án: 20
Tham lam
Đáp án: -25
Chia để trị
Đáp án: -25
Qui hoạch động
Đáp án: 20
Heuristic
Đáp án: 20
Meta-heuristic
Đáp án: 20
Học tăng cường
Đáp án: 20
Thuật toán xấp xỉ
Đáp án: -25
Tất cả các phương pháp liệt kê ở đây
Câu 4121071
Trong những nhận định dưới đây về thuật toán chia để trị và quy hoạch động, nhận định nào đúng? (có thể chọn nhiều đáp án)
Đáp án: 33.33333
Chia để trị thường được cài đặt bằng kỹ thuật đệ quy
Đáp án: 33.33333
Quy hoạch động có thể được cài đặt bằng vòng lặp
[0]
Trong quá trình giải bài toán, cả chia để trị và quy hoạch động đều cho độ phức tạp thuật toán trong thời gian đa thức
Đáp án: 33.33333
Chia để trị chia bài toán lớn thành các bài toán con độc lập, trong khi đó quy hoạch động thì chia bài toán lớn thành các bài toán con gối nhau
Câu 4121072
Đại dịch COVID19 diễn ra phức tạp trên toàn thế giới. Việt Nam cũng không phải là ngoại lệ. Rất nhiều người đã bị chết vì dịch bệnh. Công ty phân tích dữ liệu XTEC muốn thống kê số lượng người chết theo các độ tuổi: nhỏ hơn 15, từ 15 tới 20, từ 20 tới 40, từ 40 tới 60 và trên 60. Yêu cầu, cho trước một danh sách người chết vì dịch bệnh và độ tuổi của những người này, hãy đưa ra số lượng người chết theo các độ tuổi trên.
Bài toán này thuộc dạng bài nào trong các dạng bài sau:
Đáp án: 100
Adhoc
[0]
Chia để trị
[0]
Quy hoạch động
[0]
Thuật toán đặc thù
[0]
Thuật toán trên đồ thị
[0]
Đáp án khác
Câu 4121073
Để giải nhanh và chính xác phương trình x3 + 2021x + 2 = 0 với -1000 ≤x ≤ 1000 với sai số chấp nhận được 10-6, chúng ta sử dụng phương pháp giải nào dưới đây?
[0]
Duyệt toàn bộ
Đáp án: 100
Chia để trị
[0]
Quy hoạch động
[0]
Thuật toán đặc thù
[0]
Thuật toán trên đồ thị
[0]
Đáp án khác
Câu 4121074
Phương pháp Qui hoạch động trên Bitmask giải bài toán người du lịch cho lời giải thế nào?
[0]
Lời giải chấp nhận được (không đảm bảo tính tối ưu)
Đáp án: 100
Lời giải tối ưu
[0]
Đáp án khác
Câu 4121075
Cấu trúc dữ liệu Queue cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
Đáp án: 100
vào một đầu, ra đầu còn lại
[0]
vào và ra được từ cả hai đầu
[0]
vào và ra duy nhất một đầu
[0]
không cách nào trong các cách ở đây
[0]
đáp án khác
Câu 4149885
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \(10n^2, nlogn, 1000\sqrt {n}\)
Đáp án: 100
\(1000\sqrt {n}\), \(nlogn\), \(10n^2\)
[0]
\(nlogn\), \(1000\sqrt {n}\), \(10n^2\)
Câu 4092874
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \(10n^2, nlogn, 1000\sqrt {n}\)
Đáp án: 100
\(1000\sqrt {n}\), \(nlogn\), \(10n^2\)
[0]
\(nlogn\), \(1000\sqrt {n}\), \(10n^2\)
Câu 4149886
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^4n, n^2, nlogn, 1000\sqrt {n}, log(logn)\)
[0]
\(1000\sqrt {n}\), \(log(logn)\), \(nlogn\), \(10^4n,n^2\)
[0]
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(n^2\), \(10^4n\)
Đáp án: 100
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(10^4n,n^2\)
Câu 4149887
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^6n, n^3, \sqrt {nlogn}, \sqrt {n}, log(logn)\)
[0]
\(\sqrt {n}\), \(log(logn)\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
[0]
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(n^3\), \(10^6n\)
Đáp án: 100
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
Câu 4092875
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^4n, n^2, nlogn, 1000\sqrt {n}, log(logn)\)
[0]
\(1000\sqrt {n}\), \(log(logn)\), \(nlogn\), \(10^4n,n^2\)
[0]
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(n^2\), \(10^4n\)
Đáp án: 100
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(10^4n,n^2\)
Câu 4092876
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^6n, n^3, \sqrt {nlogn}, \sqrt {n}, log(logn)\)
[0]
\(\sqrt {n}\), \(log(logn)\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
[0]
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(n^3\), \(10^6n\)
Đáp án: 100
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
Câu 4092800
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án: 100
3
[0]
4
[0]
6
[0]
9
Câu 4121077
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
8
[0]
10
[0]
Đáp án khác
Câu 4092801
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
8
[0]
10
Câu 4121078
Cấu trúc dữ liệu Stack cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
[0]
vào một đầu, ra đầu còn lại
[0]
vào và ra được từ cả hai đầu
Đáp án: 100
vào và ra duy nhất một đầu
[0]
không cách nào trong các cách ở đây
[0]
đáp án khác
Câu 4092888
Những thuật toán tham lam nào KHÔNG CHẮC CHẮN cho lời giải tối ưu bài toán tập đoạn thẳng không giao nhau?
Đáp án: 33.33333
Bắt đầu sớm xét trước
Đáp án: -100
Kết thúc sớm xét trước
Đáp án: 33.33333
Ngắn hơn xét trước
Đáp án: 33.33333
Ít mâu thuẫn hơn xét trước
Câu 4092871
Given cubes (with their length, width and height) of 3 configurations: 3 x 2 x 3, 3 x 4 x 5 and 2 x 4 x 2. Assume the number of cubes in each configuration shape is infinite. What is the maximum height of the cubes that can be selected and arranged into a tower (the cubes can be rotated at different angles) such that the size of the upper cube a x b must be strictly smaller the size of the lower cube c x d, i.e. a < c and b < d
[0]
9
[0]
8
Đáp án: 100
12
[0]
13
[0]
10
[0]
11
Câu 4092872
Given cubes (with their length, width and height) of 3 configurations: 3 x 2 x 3, 3 x 4 x 5 and 4 x 4 x 3. Assume the number of cubes in each configuration shape is infinite. What is the maximum height of the cubes that can be selected and arranged into a tower (the cubes can be rotated at different angles) such that the size of the upper cube a x b must be strictly smaller the size of the lower cube c x d, i.e. a < c and b < d
[0]
10
[0]
9
Đáp án: 100
11
[0]
13
[0]
12
[0]
14
Câu 4092873
[0]
12
[0]
13
Đáp án: 100
14
[0]
15
[0]
16
Câu 4092889
Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
Câu 4092890
Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?
[0]
Nhánh cận
[0]
Tham lam
[0]
Qui hoạch động
[0]
Heuristic
[0]
Meta-heuristic
[0]
Học tăng cường
Đáp án: 100
Tất cả các phương pháp trên
Câu 4092891
Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?
Đáp án: 25
\(P \subseteq NP\)
Đáp án: 25
\(NPC \subseteq NP\)
Đáp án: -12.5
\(P \subset NP\)
Đáp án: -12.5
\(P \neq NP\)
Đáp án: -12.5
\(P = NP\)
Đáp án: -12.5
\(NPC = NP\)
Đáp án: -12.5
\(NPC \subset NP\)
Đáp án: -12.5
\(NPC \neq NP\)
Đáp án: 25
\(NPC \subset NP\)-khó
Đáp án: 25
\(NP\)-khó \(\cap NP = NPC\)
Đáp án: -12.5
\(NP \subset NP\)-khó
Đáp án: -12.5
\(P \neq NP\)-khó
Câu 4121079
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
9
[0]
8
Đáp án: 100
12
[0]
13
[0]
10
[0]
11
[0]
Đáp án khác
Câu 4149882
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
9
[0]
8
Đáp án: 100
12
[0]
13
[0]
10
[0]
11
Câu 4121080
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
10
[0]
9
Đáp án: 100
11
[0]
13
[0]
12
[0]
14
[0]
Đáp án khác
Câu 4149883
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
10
[0]
9
Đáp án: 100
11
[0]
13
[0]
12
[0]
14
Câu 4121081
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
12
[0]
13
Đáp án: 100
14
[0]
15
[0]
16
[0]
Đáp án khác
Câu 4149884
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
[0]
12
[0]
13
Đáp án: 100
14
[0]
15
[0]
16
Câu 4121082
Nếu công thức truy hồi độ phức tạp tính toán của phương pháp tìm kiếm nhị phân (binary search) được biểu diễn dưới dạng \(T(n)=aT(n/b)+O(n^d)\) thì giá trị \(a+b+d\) là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án.
Đáp án: 100
Câu 4121083
Biết rằng hàm số f(x) = x19 - x2 - x + 1 có một nghiệm nằm trong khoảng [0, 1], bạn được yêu cầu lập trình để tìm và điền nghiệm trên với sai số 10-6 vào ô trống.
Đáp án: 100
Câu 4121084
Có bao nhiêu cách chia 20 cái kẹo cho 9 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121085
Có bao nhiêu cách chia 21 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121086
Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121087
Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121088
Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121089
Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100"
Câu 4121090
Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121091
Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Đáp án: 100
Câu 4121092
Cho dãy số nguyên [-9, 17, -16, -50, 19, -26, 28, 8, 12, 14, -45, -5, 31, -23, 11, 41, 45, -8, -23, -14], hãy tìm một đoạn con các phần tử liên tiếp trong dãy sao cho tổng mũ 3 của các phần tử trong đoạn con là lớn nhất và điền giá trị tổng này vào ô trống
Đáp án: 100
Câu 4092892
Có tồn tại thuật toán tham lam cho kết quả tối ưu với mọi bộ dữ liệu bài toán cái túi hay không?
Đáp án: 0
Có
Đáp án: 100
Không
Câu 4149888
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Đáp án: 0
Yes
Đáp án: 100
No
Câu 4092877
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Đáp án: 0
Yes
Đáp án: 100
No
Câu 4092893
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Đáp án: 0
Yes
Đáp án: 100
No
Câu 4092894
Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?
Đáp án: 100
Có
Đáp án: 0
Không
Câu 0
Câu 4084602
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)Đáp án: 100
1 --> 6 --> 4
Đáp án: -25
1 --> 2 --> 5 --> 4
Đáp án: -25
Đáp án: -25
1 --> 3--> 2 --> 5 --> 4
Đáp án: -25
1 --> 5 --> 4
Câu 4084603
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)Đáp án: 100
2
Đáp án: -25
1
Đáp án: -25
Đáp án: -25
4
Đáp án: -25
5
Câu 4084604
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)Đáp án: 100
1 --> 2 --> 4 --> 6
Đáp án: -25
1 --> 3 --> 5 --> 7 --> 6
Đáp án: -25
Đáp án: -25
1 --> 3--> 5 --> 6
Đáp án: -25
1 --> 5 --> 7 --> 6
Câu 4084605
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)Đáp án: 100
a --> b --> d --> f
Đáp án: -25
a --> c --> e --> g --> f
Đáp án: -25
Đáp án: -25
a --> c--> e --> f
Đáp án: -25
a --> e --> g --> f
Câu 4084606
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)
Đáp án: 100
Đáp án: -25
Đáp án: -25
Đáp án: -25
Câu 4084607
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)
Đáp án: 100
Đáp án: -25
Đáp án: -25
Đáp án: -25
Câu 0
Câu 0
Câu 0
Câu 0
Câu 0
Câu 0
Câu 4135454
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4135455
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4135456
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4092386
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4092387
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4092388
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 0
Câu 0
Câu 4149811
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án: 100
3
[0]
4
[0]
6
[0]
9
[0]
Đáp án khác
Câu 4149812
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
8
[0]
10
[0]
Đáp án khác
Câu 0
Câu 4149838
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian bắt đầu \(S_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?
Đáp án: -50
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án: 50
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án: 50
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
Đáp án: -50
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
[0]
Đáp án khác
Câu 4149839
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian kết thúc \(F_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?
Đáp án: 25
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
Đáp án: 25
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
[0]
Đáp án khác
Câu 4149840
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của tổng thời gian thực hiện công việc \(F_j - S_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?
Đáp án: 50
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)
Đáp án: 50
\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)
Đáp án: -50
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)
Đáp án: -50
\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)
[0]
Đáp án khác
Câu 4149841
Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
- Với mỗi công việc \(j\), tính \(C_j\) là số lượng công việc không tương thích với \(j\). Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của \(C_j\);
- Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.
Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?
Đáp án: 50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án: 50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)
Đáp án: -50
\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án: -50
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
[0]
Đáp án khác
Câu 0
Câu 4149842
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không tăng của giá trị;
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và xếp đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\)).
Đáp án: 50
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)
Đáp án: -50
\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)
Đáp án: 50
\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)
Đáp án: -50
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)
[0]
Đáp án khác
Câu 4149843
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không giảm của trọng lượng;
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Đáp án: -50
\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án: 50
\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
Đáp án: 50
\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)
Đáp án: -50
\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)
[0]
Đáp án khác
Câu 4149844
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
- Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng lượng (\(C_i /W_i\)), nghĩa là \[\frac {C_{i_1}}{W_{i_1}} \ge \frac {C_{i_2}}{W_{i_2}} \ge \ldots\le \frac {C_{i_n}}{W_{i_n}};\]
- Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Đáp án: -50
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)
Đáp án: 50
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)
Đáp án: -50
\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)
Đáp án: 50
\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)
[0]
Đáp án khác
Câu 0
Câu 4149845
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 3 có giá vé là 90 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 3 thành phố khác
- Bus từ thành phố 5 có giá vé là 20 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 6 có giá vé là 20 và có thể đi đến nhiều nhất 5 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
50
[0]
60
Đáp án: 100
70
[0]
80
[0]
90
[0]
Đáp án khác
Câu 4149846
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 1 thành phố khác
- Bus từ thành phố 3 có giá vé là 40 và có thể đi đến nhiều nhất 3 thành phố khác
- Bus từ thành phố 4 có giá vé là 60 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 5 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
40
Đáp án: 100
50
[0]
60
[0]
70
[0]
80
[0]
Đáp án khác
Câu 4149847
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
- Thành phố 1 nối với thành phố 2
- Thành phố 1 nối với thành phố 5
- Thành phố 3 nối với thành phố 5
- Thành phố 3 nối với thành phố 6
- Thành phố 4 nối với thành phố 5
- Thành phố 4 nối với thành phố 6
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
- Bus từ thành phố 1 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 3 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 2 thành phố khác
- Bus từ thành phố 5 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
- Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
[0]
10
[0]
20
Đáp án: 100
30
[0]
40
[0]
50
[0]
Đáp án khác
Câu 0
Câu 4149856
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0]
26
[0]
27
Đáp án: 100
28
[0]
29
[0]
30
[0]
Đáp án khác
Câu 4149857
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
Đáp án: 100
24
[0]
25
[0]
26
[0]
27
[0]
28
[0]
Đáp án khác
Câu 4149858
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
[0]
16
Đáp án: 100
18
[0]
19
[0]
23
[0]
Đáp án khác
Câu 0
Câu 4149864
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
[0]
Đáp án khác
Câu 4149865
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
Đáp án: 100
NP-đầy đủ
[0]
P
[0]
Đáp án khác
Câu 4149866
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này.
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
[0]
NP-đầy đủ
Đáp án: 100
P
[0]
Đáp án khác
Câu 4149867
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
[0]
Đáp án khác
Câu 4149868
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
Đáp án: 100
NP-đầy đủ
[0]
P
[0]
Đáp án khác
Câu 4149869
Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
NP
[0]
NP-khó
[0]
NP-đầy đủ
Đáp án: 100
P
[0]
Đáp án khác
Câu 0
Câu 4149889
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
6
[0]
Đáp án khác
Câu 4149890
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
6
[0]
Không có phương án nào thực hiện được
Câu 4149891
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
[0]
2
[0]
3
Đáp án: 100
4
[0]
5
[0]
Đáp án khác
Câu 4149892
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
5
[0]
Không có phương án thực hiện
Câu 0
Câu 4149895
Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?
Đáp án: -50
Đồ thị tổng quát
Đáp án: 25
Đồ thị không chứa chu trình âm
Đáp án: 25
Đồ thị không có cạnh trọng số âm
Đáp án: 25
Đồ thị có hướng không có chu trình DAG
Đáp án: 25
Cây
Đáp án: -50
Đồ thị hai phía
[0]
Đáp án khác
Câu 4149897
Những mệnh đề nào sau đây là ĐÚNG?
Đáp án: 50
Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó
Đáp án: -50
Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó
Đáp án: -50
Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)
Đáp án: 50
Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)
[0]
Không đáp án nào đúng
Câu 4149898
Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?
Đáp án: -25
Nhánh cận
Đáp án: 20
Tham lam
Đáp án: -25
Chia để trị
Đáp án: -25
Qui hoạch động
Đáp án: 20
Heuristic
Đáp án: 20
Meta-heuristic
Đáp án: 20
Học tăng cường
Đáp án: 20
Thuật toán xấp xỉ
Đáp án: -25
Tất cả các phương pháp liệt kê ở đây
[0]
Không đáp án nào đúng
Câu 4149900
Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?
[0]
NP
Đáp án: 100
NP-khó
[0]
NP-đầy đủ
[0]
P
[0]
Đáp án khác
Câu 4149901
Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?
[0]
Nhánh cận
[0]
Tham lam
[0]
Qui hoạch động
[0]
Heuristic
[0]
Meta-heuristic
[0]
Học tăng cường
Đáp án: 100
Tất cả các phương pháp trên
Câu 4149902
Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?
Đáp án: 25
\(P \subseteq NP\)
Đáp án: 25
\(NPC \subseteq NP\)
Đáp án: -12.5
\(P \subset NP\)
Đáp án: -12.5
\(P \neq NP\)
Đáp án: -12.5
\(P = NP\)
Đáp án: -12.5
\(NPC = NP\)
Đáp án: -12.5
\(NPC \subset NP\)
Đáp án: -12.5
\(NPC \neq NP\)
Đáp án: 25
\(NPC \subset NP\)-khó
Đáp án: 25
\(NP\)-khó \(\cap NP = NPC\)
Đáp án: -12.5
\(NP \subset NP\)-khó
Đáp án: -12.5
\(P \neq NP\)-khó
[0]
Đáp án khác
Câu 4149905
Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?
Đáp án: 100
Có
Đáp án: 0
Không
Câu 0
Câu 4149906
Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$.
Đáp án: 100">
Câu 4121076
Trong một phiên bản giải thuật quicksort dùng phần tử ở vị trí thứ n/5 làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?
[0]
\(O(nlogn)\)
[0]
\(O(n^5logn)\)
[0]
\(O(nlog^5n)\)
Đáp án: 100
\(O(n^2)\)
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4098514
Phát biểu nào sau đây về quy lui (backtracking) là đúng?
[0]
Bài toán sinh tất cả các xâu nhị phân có độ dài cho trước không thể giải được bằng thuật toán quay lui
Đáp án: 100
Thuật toán quay lui có thể tìm ra giải pháp tối ưu cho bài toán tối ưu hóa tổ hợp
[0]
Thuật toán quay lui luôn có độ phức tạp thời gian tính toán đa thức
[0]
Thuật toán quay lui không thể tìm thấy bất kỳ lời giải tối ưu nào cho một bài toán tối ưu hóa tổ hợp
[0]
Đáp án khác
Câu 0
Câu 4098577
Cho đồ thị vô hướng G = (V, E), với V là tập đỉnh và E là tập cạnh. Ký hiệu, A[x] là tập các đỉnh kề với đỉnh x, với mọi x thuộc V.
Cho một hàm (được miêu tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào:
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
for v in A(u) do{
if d[v] = -1 then{
Q.push(v);
d[v] = d[u] + 1;
}
}
}
return d[t];
}
Phát biểu nào dưới đây là đúng?
Đáp án: 100
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
[0]
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
[0]
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
[0]
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
[0]
Đáp án khác
Câu 0
Câu 4098591
Cho đoạn chương trình dưới đây (miêu tả bằng mã giả), trong đó mảng a (các phần tử được đánh chỉ số từ 1 tới n), các biến toàn cục (global variables) n, m, T, cnt (a, n, m là tham số đầu vào)
solve(k){
for v = 0 to 1 do{
T = T + v*a[i];
if k = n then{
if T = m then
cnt = cnt + 1;
}else
solve(k+1);
}
}
main{
T = 0;
cnt = 0;
solve(1);
print(cnt);
}
Phát biểu nào dưới đây là đúng?
[0]
Chương trình tính số cách chọn các phần tử sao cho tổng các phần tử được chọn bằng m
[0]
Chương trình kiểm tra xem tổng các phần tử của a có bằng m không?
[0]
Chương trình tính số lần giá trị m xuất hiện trong mảng a
Đáp án: 100
Đáp án khác
Câu 0
Câu 4098601
Cho đồ thị vô hướng G = (V, E), trong đó V là tập đỉnh và E là tập cạnh. Ký hiệu A[x] là tập các đỉnh kề với đỉnh x (với mọi x thuộc V).
Cho hàm (được mô tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào.
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
print(u);
for v in A(u) do{
Q.push(v);
d[v] = d[u] + 1;
}
}
return d[t];
}
Phát biểu nào sau đây là đúng?
Đáp án: 100
Đáp án khác
[0]
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều rộng
[0]
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều sâu
[0]
Chương trình kết thúc và trả về độ dài (số cạnh) của đường đi ngắn nhất từ s tới t trên G
Câu 0
Câu 4098624
Cho một cây T = (V, E), trong đó V = {1,2,3,4,5,6,7,8,9,10,11,12,13} là tập các đỉnh và E = {(1,2), (1,12), (1,13), (2,3), (2,4), (3,7), (3,8), (3,9), (4,5), (4,6), (5,10), (5,11)} là tập các cạnh. Các đỉnh 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 lần lượt có trọng số 8, 6, 9, 1, 9, 2, 10, 2, 4, 3, 2, 5, 7. Tìm một tập con S các đỉnh trong V có tổng các trọng số lớn nhất sao cho 2 đỉnh bất kỳ trong S không kề nhau trên T. Tổng các trọng số các đỉnh trong S bằng bao nhiêu?
Đáp án: 100
37
[0]
35
[0]
38
[0]
39
[0]
43
[0]
45
[0]
46
[0]
Đáp án khác
Câu 0
Câu 4098639
Cho đoạn chương trình được miêu tả bởi một đoạn mã giả dưới đây, trong đó hàm P nhận một mảng a, n, W, T, k như tham số (thành phần của mảng a được đánh chỉ số từ 1 tới n) và cnt là một biến toàn cục.
P(a, n, W, T, k){
for v = 0 to 1 do {
if (k = n) then{
if (T + v*a[k] = W) then cnt = cnt + 1;
}else
P(a, n, W, T + v*a[k], k+1);
}
}
Main { // main function
a = {2,3,6,7,4,5}; // array indexed from 1 to 6
cnt = 0;
P(a, 6, 12, 0, 1);
print(cnt); // print the value cnt to the screen
}
Giá trị của cnt được in ra màn hình trong hàm Main là bao nhiêu?Đáp án: 100
4
[0]
2
[0]
3
[0]
5
[0]
6
[0]
8
[0]
9
[0]
Đáp án khác
Câu 0
Câu 4098649
Mỗi phần tử của một Min-Heap (được biểu diễn bởi một cây đầy đủ) có hai trường (id, k), trong đó id là định danh và k là khóa của phần tử. Min-Heap có các hàm (operations) sau:
- insertHeap(id, k): Chèn 1 phần tử với định danh id và khóa k vào trong Min-Heap
- deleteMin(): Trả về phần tử (id, k) có khóa nhỏ nhất và xóa phần tử này ra khỏi Min-Heap
- updateKey(id, k): Cập nhật phần tử có định danh id với giá trị khóa mới k
Hiện hiện một chuỗi các thao tác sau trên Min-Heap:
- insertHeap(1,4)
- insertHeap(2,9)
- insertHeap(3,3)
- insertHeap(4,7)
- insertHeap(5,6)
- insertHeap(6,1)
- insertHeap(7,2)
- insertHeap(8,5)
- insertHeap(9,10)
- deleteMin()
Phát biểu nào dưới đây là đúng?
Đáp án: 100
Phần tử có định danh 4 là con phải của phần tử có định danh 8
[0]
Phần tử có định danh 4 là con trái của phần tử có định danh 8
[0]
Phần tử có định danh 2 là con phải của phần tử có định danh 8
[0]
Phần tử có định danh 2 là con trái của phần tử có định danh 8
[0]
Phần tử có định danh 1 là con phải của phần tử có định danh 7
[0]
Phần tử có định danh 1 là con trái của phần tử có định danh 7
[0]
Đáp án khác
Câu 0
Câu 4135446
Hãy ghép cặp thuật toán với bài toán phù hợp.
Thuật toán Dijkstra
Thuật toán Prim
Thuật toán Kruskal
Câu 4135515
Có thể xây dựng được bao nhiêu đồ thị vô hướng (không nhất thiết phải liên thông) với n đỉnh?
[0]
n(n-1)
[0]
[0]
2n
[0]
n!
Đáp án: 100
2(n(n-1)/2
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4135447
Cho đồ thị vô hướng với trọng số \( G \) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \( G \).
Đáp án: 100
Câu 4135448
Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án: 100
Câu 4135449
Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án: 100
Câu 4135450
Xét đồ thị có trọng số \(G\)như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Đáp án: 100
Câu 0
Câu 4135451
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4135452
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 4135453
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.
Đáp án: 100
Đáp án: 100
Đáp án: 100
Đáp án: 100
Câu 0
Câu 0
Câu 4135457
Cho đồ thị vô hướng trọng số trên cạnh như dưới đây
Hỏi có tồn tại cây khung nhỏ nhất mà không chứa đồng thời hai cạnh \(a-b\) và \(a-c\) hay không?
Đáp án: 0
Có
Đáp án: 100
Không
Câu 4135458
Cho đồ thị vô hướng với trọng số trên cạnh như dưới đây
Hỏi có tồn tại cây khung nhỏ nhất chứa cạnh \(d-f\) hay không?
Đáp án: 0
Có
Đáp án: 100
Không
Câu 0
Câu 0
Câu 0
Câu 4135459
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 30 cạnh đều có bậc là 3 hoặc 5.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=5}
Câu 4135461
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 15 đỉnh và 25 cạnh đều có bậc là 2 hoặc 7.
Do đó, số đỉnh có bậc là 2 của đồ thị G = {1:NUMERICAL:=11}
Câu 4135463
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 54 cạnh đều có bậc là 3 hoặc 7.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=8}
Câu 4135465
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 52 cạnh đều có bậc là 4 hoặc 7.
Do đó, số đỉnh có bậc là 4 của đồ thị G = {1:NUMERICAL:=12}
Câu 0
Câu 0
Câu 0
Câu 0
Câu 4135467
Thuật toán nào dưới đây hiệu quả nhất để tìm đường đi đơn ngắn nhất giữa 2 trong đồ thị tổng quát?
Đáp án: 100
Đáp án khác
[0]
Dijkstra
[0]
Bellman-Ford
[0]
Floyd-Warshall
[0]
Prim
[0]
Kruskal
Câu 0
Câu 0
Câu 0
Câu 4135468
Cho đồ thị có hướng như trên hình vẽ:
Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
Đáp án: 100
D
[0]
E
[0]
F
Câu 4135469
Cho đồ thị có hướng như trên hình vẽ:
Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:
[0]
E, D, F, C, B
[0]
E, D, C, B, F
[0]
E, C, B, F, D
[0]
E, C, B, D, F
Đáp án: 100
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135470
Cho đồ thị có hướng như trên hình vẽ:
Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:
Đáp án: 100
E, D, B, F, C
[0]
E, D, C, B, F
[0]
E, C, B, F, D
[0]
E, C, B, D, F
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135471
Cho đồ thị có hướng như trên hình vẽ:
Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
[0]
D
[0]
E
Đáp án: 100
F
Câu 4135472
Cho đồ thị có hướng như trên hình vẽ:
Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:
[0]
C, E, B, D, F
[0]
C, E, F, D, B
[0]
C, F, E, D, B
[0]
C, F, E, B, D
Đáp án: 100
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135473
Cho đồ thị có hướng như trên hình vẽ:
Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
Đáp án: 100
C
[0]
D
[0]
E
[0]
F
Câu 4135474
Cho đồ thị như trên hình vẽ:
Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ đỉnh A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
[0]
B
[0]
C
[0]
D
Đáp án: 100
E
[0]
F
Câu 4135475
Cho đồ thị có hướng như trên hình vẽ:
Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Đáp án: 100
B
[0]
C
[0]
D
[0]
E
[0]
F
Câu 0
Câu 0
Câu 0
Câu 4135476
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[6] bằng bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
6
[0]
1
[0]
3
[0]
Đáp án khác
Câu 4135477
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[11] bằng bao nhiêu?
[0]
4
[0]
5
Đáp án: 100
6
[0]
1
[0]
3
[0]
Đáp án khác
Câu 4135478
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11), (10, 11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[10] bằng bao nhiêu?
Đáp án: 100
4
[0]
5
[0]
6
[0]
1
[0]
3
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4135479
Hãy xác định đâu là cây tìm kiếm theo chiều sâu xuất phát từ đỉnh 1 (kí hiệu là DFS(1)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án: 100
[0]
[0]
[0]
[0]
[0]
Câu 4135480
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 3 (kí hiệu là DFS(3)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án: 100
[0]
[0]
[0]
[0]
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135481
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 2 (kí hiệu là DFS(2)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1, 2 ,3, 4, 5, 6, 7, 8.
[0]
Đáp án: 100
Đáp án: -25
[0]
[0]
[0]
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135482
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 4 (kí hiệu là DFS(4)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Đáp án: 100
[0]
[0]
[0]
[0]
[0]
Câu 0
Câu 4135483
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 4 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 4 đến đỉnh 7 là:
Đáp án: 100
4 --> 2 --> 5 --> 7
[0]
4 --> 5 --> 7
[0]
4 --> 2 --> 6 --> 7
[0]
4 --> 2 --> 8 --> 6 --> 7
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135484
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
[0]
1 --> 4 --> 5 --> 7 --> 6
[0]
1 --> 2 --> 6
[0]
1 --> 2 --> 8 --> 6
[0]
1 --> 2 --> 5 --> 7 --> 6
Đáp án: 100
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Câu 4135485
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
Đáp án: 100
1 --> 2 --> 4 --> 5 --> 7 -->6
[0]
1 --> 2 --> 6
[0]
1 --> 2 --> 8 --> 6
[0]
1 --> 2 --> 5 --> 7 --> 6
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Câu 4135486
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
[0]
3 --> 4 --> 5 --> 7 -->6
[0]
3 --> 1 --> 2 --> 6
[0]
3 --> 4 --> 2 --> 6
[0]
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
Đáp án: 100
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Đáp án: -25
3 --> 4 --> 2 -->8 --> 6
Câu 4135487
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
Đáp án: 100
2 --> 1 --> 4 --> 5 --> 7
[0]
2 --> 8 --> 6 --> 7
[0]
2 --> 5 --> 7
[0]
2 --> 1 --> 8 --> 6 --> 7
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 4135488
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
Đáp án: 100
3 --> 1 --> 2 --> 4 --> 5 --> 7 -->6
[0]
3 --> 1 --> 2 --> 6
[0]
3 --> 4 --> 2 --> 6
[0]
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
[0]
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
[0]
3 --> 4 --> 2 -->8 --> 6
Câu 4135489
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
[0]
2 --> 4 --> 5 --> 7
[0]
2 --> 8 --> 6 --> 7
[0]
2 --> 5 --> 7
[0]
2 --> 1 --> 8 --> 6 --> 7
Đáp án: 100
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Câu 0
Câu 0
Câu 0
Câu 4135490
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án: 100
1 --> 6 --> 4
[0]
1 --> 2 --> 5 --> 4
[0]
[0]
1 --> 3--> 2 --> 5 --> 4
[0]
1 --> 5 --> 4
[0]
Đáp án khác
Câu 4135491
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án: 100
1 --> 2 --> 4 --> 6
[0]
1 --> 3 --> 5 --> 7 --> 6
[0]
[0]
1 --> 3--> 5 --> 6
[0]
1 --> 5 --> 7 --> 6
[0]
Đáp án khác
Câu 4135492
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
Đáp án: 100
a --> b --> d --> f
[0]
a --> c --> e --> g --> f
[0]
[0]
a --> c--> e --> f
[0]
a --> e --> g --> f
[0]
Đáp án khác
Câu 0
Câu 4135493
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?
Đáp án: 100
2
[0]
1
[0]
[0]
4
[0]
5
[0]
Đáp án khác
Câu 0
Câu 4135494
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
Đáp án: 100
[0]
[0]
[0]
[0]
Đáp án khác
Câu 4135495
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:
Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
Đáp án: 100
[0]
[0]
[0]
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4135496
Chúng ta có thể sử dụng các phương pháp tìm kiếm nào dưới đây để tìm tất cả các thành phần liên thông trong đồ thị vô hướng có trọng số G = (V,E, c)?
[0]
Tìm kiếm theo chiều rộng (BFS)
[0]
Tìm kiếm theo chiều sâu (DFS)
Đáp án: 100
Tìm kiếm theo chiều rộng và chiều sâu
[0]
Đáp án khác
Câu 4135497
Thuật toán nào dưới đây là phù hợp nhất để tìm thành phần liên thông mạnh trong một đồ thị có trọng số?
[0]
Thuật toán tìm kiếm theo chiều rộng
Đáp án: 100
Thuật toán tìm kiếm theo chiều sâu
[0]
Thuật toán tìm kiếm theo chiều rộng và chiều sâu
[0]
Đáp án khác
[0]
Thuật toán dijkstra
Câu 4135498
Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị có hướng không trọng số G = (V, E) thì dùng thuật toán nào dưới đây phù hợp nhất?
Chú ý đường đi ngắn nhất giữa 2 đỉnh là đường đi qua ít cạnh nhất.
Đáp án: 100
Tìm kiếm theo chiều rộng
[0]
Tìm kiếm theo chiều sâu
[0]
Thuật toán dijkstra
[0]
Thuật toán Bellman-Ford
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4135553
Nhận định nào dưới đây là đúng khi so sánh biểu diễn đồ thị theo danh sách kề với biểu diễn đồ thị theo ma trận kề?
[0]
Biểu diễn theo danh sách kề sẽ tiết kiệm bộ nhớ hơn cho những ma trận thưa
[0]
DFS và BFS có thể thực hiện trong O(V+E) nếu sử dụng biểu diễn theo danh sách kề. Trong khi đó, nếu biểu diễn theo ma trận kề thì các thao tác này có độ phức tạp O(V2). Trong đó V, E lần lượt là số lượng đỉnh và cạnh của đồ thị.
[0]
Thêm một đỉnh vào đồ thị sẽ dễ dàng hơn khi biểu diễn theo danh sách kề so với biểu diễn đồ thị theo ma trận kề
Đáp án: 100
Tất cả các đáp án trên
Câu 0
Câu 4136594
Dãy bậc của một đơn đồ thị là dãy bậc của các đỉnh của đồ thị đó được sắp xếp giảm dần. Dãy nào sau đây không thể là dãy bậc của đồ thị nào đó?
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
Đáp án: 100
II và IV
[0]
I và II
[0]
III và IV
[0]
IV
[0]
Đáp án khác
Câu 0
Câu 4136623
Thuật toán hiệu quả nhất để tìm số lượng các thành phần liên thông trong một đồ thị vô hướng trên n đỉnh và m cạnh có độ phức tạp về thời gian là bao nhiêu?
[0]
θ(n)
[0]
θ(m)
Đáp án: 100
θ(m + n)
[0]
θ(mn)
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4136656
Số lượng cạnh đối đa trong một chu trình trên một đồ thị vô hướng không chu trình gồm n đỉnh là bao nhiêu?
Đáp án: 100
n-1
[0]
n
[0]
n+1
[0]
2n-1
[0]
Đáp án khác
Câu 0
Câu 4136716
Xét một đồ thị có hướng với n đỉnh và m cạnh sao cho tất cả các cạnh đều có trọng số các cạnh bằng nhau. Tìm độ phức tạp của thuật toán đã biết tốt nhất để tính cây khung nhỏ nhất của đồ thị?
Đáp án: 100
O(m+n)
[0]
O(m logn)
[0]
O(mn)
[0]
O(n logm)
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4136724
Gọi G là một đồ thị đơn giản có 20 đỉnh và 8 thành phần liên thông. Nếu chúng ta xóa một đỉnh trong G, thì số thành phần trong G sẽ nằm trong khoảng nào dưới đây?
Đáp án: 100
7 - 19
[0]
8-20
[0]
8-19
[0]
7-20
[0]
Đáp án khác
Câu 0
Câu 4136729
Cấu trúc dữ liệu nào dưới đây phù hợp với duyệt độ thị theo chiều rộng?
[0]
Ngăn xếp
Đáp án: 100
Hàng đợi
[0]
Danh sách liên kết
[0]
Đáp án khác
Câu 0
Câu 0
Câu 4136795
Để cài đặt thuật toán đường đi ngắn nhất Dijkstra trên đồ thị không có trọng số để nó chạy trong thời gian tuyến tính, cấu trúc dữ liệu sẽ được sử dụng là:
Đáp án: 100
Hàng đợi
[0]
Ngăn xếp
[0]
Đống (Heap)
[0]
B-Tree
Câu 0
Câu 4121034
Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.
Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?
[0]
3
Đáp án: 100
4
[0]
5
[0]
6
[0]
Đáp án khác